package com.sicheng.蓝桥.练习题.线段树;


/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/25 12:14
 */
public class 区间覆盖 {

    private final int N = (int) 1e8;
    private int n = N;
    private final int[] cover = new int[N << 2];
    private final int[] tree = new int[N << 2];

    public void add(int l, int r) {
        add(l, r, 1, n, 1);
    }

    private void pushUp(int st) {
        tree[st] = tree[st << 1] + tree[st << 1 | 1];
    }

    private void add(int l, int r, int ll, int rr, int st) {
        if (cover[st] == 1) {
            return;
        }
        if (l == ll && r == rr) {
            cover[st] = 1;
            tree[st] = r - l + 1;
            return;
        }

        int mid = ll + rr >> 1;
        if (r <= mid) {
            add(l, r, ll, mid, st << 1);
        } else if (l > mid) {
            add(l, r, mid + 1, rr, st << 1 | 1);
        } else {
            add(l, mid, ll, mid, st << 1);
            add(mid + 1, r, mid + 1, rr, st << 1 | 1);
        }
        pushUp(st);
    }

    public int count() {
        return tree[1];
    }

    public static void main(String[] args) {
        区间覆盖 solution = new 区间覆盖();
        solution.n = 100;
        solution.add(1, 2);
        System.out.println(solution.count());
        solution.add(1, 4);
        solution.add(5, 6);
        System.out.println(solution.count());
        System.out.println(solution.count());

    }

}
